#include <iostream>
#include <string>
#include <memory>
#define MAX_VARIABLE_NUM 26
#define STACK_INIT_SIZE 128
#define STACK_INCREMENT 32
using namespace std;

// (~AB+C)~D+D
// 栈用于解析逻辑表达式。方便起见，使用顺序栈。

typedef struct Stack
{
    char *base;
    char *top;
    int stacksize;
} Stack, Queue;

typedef struct Node
{
    bool input[MAX_VARIABLE_NUM];
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node, *BinaryTree;

void Exit(string message)
{
    cout << "ERROR:" << message << endl;
    exit(1);
}

//初始化栈
void InitStack(Stack &S)
{
    S.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
    if (!S.base)
        Exit("Memory Deficiency");
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}

//弹出并返回栈顶元素
template <class T>
bool Pop(Stack &S, T &e)
{
    if (S.top == S.base)
        return 0;
    e = *--S.top;
    return 1;
}

//入栈
void Push(Stack &S, char e)
{
    if (S.top - S.base >= S.stacksize)
    {
        S.base = (char *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(char));
        if (!S.base)
            Exit("Stack Overflow");
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *S.top++ = e;
}

//判断栈是否空，空的话返回1， 否则返回0
bool IsStackEmpty(Stack &S)
{
    if (S.base == S.top)
    {
        return 1;
    }
    return 0;
}

void InQueue(Queue &Q, char e)
{
    Push(Q, e);
}

bool OutQueue(Queue &Q, char &e)
{
    if (Q.base == Q.top)
        return 0;
    e = *Q.base++;
    return 1;
}

void Duplicate(Stack &S1, Stack &S2)
{
    //拷贝S1中的内容到S2中去
    char *start = S1.base;
    while (start != S1.top)
    {
        *S2.top++ = *start++;
    }
}

//求后缀表达式
void Polish(string equation, string &polish_equation)
{
    Stack tmp;
    char e;
    int left_brc = 0;
    int right_brc = 0;
    InitStack(tmp);
    for (int i = 0; i < equation.length(); i++)
    {
        if (equation[i] == ')')
        {
            right_brc++;
            while (Pop<char>(tmp, e))
            {
                if (e == '(')
                {
                    break;
                }
                polish_equation.append(1, e);
            }
            continue;
        }
        if (equation[i] == '(')
        {
            left_brc++;
            if (*(tmp.top - 1) == ')')
            {
                Push(tmp, '*');
            }
            Push(tmp, '(');
            continue;
        }
        if (equation[i] == '+')
        {
            polish_equation.append(1, *(--tmp.top));
            Push(tmp, equation[i]);
            continue;
        }
        if (equation[i] == '*' && (*(tmp.top - 1) == '*' || *(tmp.top - 1) == '+'))
        {
            polish_equation.append(1, *(--tmp.top));
            Push(tmp, equation[i]);
            continue;
        }
        if (equation[i] == '~')
        {
            Push(tmp, equation[i]);
            continue;
        }
        if (equation[i] >= 65 && equation[i] <= 90)
        {
            if (i >= 0 && equation[i - 1] >= 65 && equation[i - 1] <= 90 || i >= 0 && equation[i - 1] == '~' && equation[i - 2] >= 65 && equation[i - 2] <= 90)
            {
                // 像AB或者A~B这样式子要将隐式表达的*入栈
                if (*(tmp.top - 1) == '~' || *(tmp.top - 1) == '*')
                {
                    polish_equation.append(1, *(tmp.top - 1));
                    tmp.top--;
                }
                    Push(tmp, '*');
            }
            polish_equation.append(1, equation[i]);
        }
    }
    if (left_brc != right_brc)
    {
        Exit("Unpaired Brackets");
    }
    while (Pop<char>(tmp, e))
    {
        polish_equation.append(1, e);
    }
}

bool Get(Node &n, char c)
{
    return n.input[c - 65];
}

bool Parse(Node n, string &polish_equation)
{
    char e;
    bool num1;
    bool num2;
    Stack tmp; //用于计算
    InitStack(tmp);
    for (int i = 0; i < polish_equation.length(); i++)
    {
        switch (polish_equation[i])
        {
        case '~':
            Pop<bool>(tmp, num1);
            Push(tmp, !num1);
            break;
        case '*':
            Pop<bool>(tmp, num1);
            Pop<bool>(tmp, num2);
            Push(tmp, num1 * num2);
            break;
        case '+':
            Pop<bool>(tmp, num1);
            Pop<bool>(tmp, num2);
            Push(tmp, num1 + num2);
            break;
        default:
            Push(tmp, Get(n, polish_equation[i]));
        }
    }
    Pop(tmp, num1);
    return num1;
}


void test(string equation)
{
    string polish_equation;
    Polish(equation, polish_equation);
    cout << polish_equation;
    cout << endl;
    Node n;
    for (int i = 0; i < MAX_VARIABLE_NUM; i++)
    {
        n.input[i] = 0;
    }
    n.input[0] = 0;
    n.input[1] = 0;
    n.input[2] = 1;
    n.input[3] = 0;
    cout << "Expecting 0 for input 0000, and we get: " << Parse(n, polish_equation) << endl;
    n.input[0] = 1;
    n.input[1] = 1;
    n.input[2] = 1;
    n.input[3] = 1;
    cout << "Expecting 1 for input 1111, and we get: " << Parse(n, polish_equation) << endl;
    cout << endl
         << "Test Completed" << endl;
    exit(0);
}

int main()
{
    string equation;
    cout << "Enter Equation" << endl;
    cin >> equation;
    test(equation);
}